/****************************************************
          File Name:binary_tree.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Sun 15 Mar 2015 09:54:20 AM CST
*****************************************************/

#include "binary_tree.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

PTree BuildTree(PTree tree)
{
    char ch = 0;
    ch = getchar();
    if(ch == '#')
        tree = NULL;
    else
    {
        tree = (Tree *)malloc(sizeof(Tree));
        if(!tree)
        {
            printf("malloc failed\n");
            exit(1);
        }
        tree->data = ch;
        tree->lchild= BuildTree(tree->lchild);
        tree->rchild= BuildTree(tree->rchild);
    }
    return tree;
}

void PreOrderTraverse(PTree tree)
{
    if(tree)
    {
        printf("%c ", tree->data);
        PreOrderTraverse(tree->lchild);
        PreOrderTraverse(tree->rchild);
    }
}

void InOrderTraverse(PTree tree)
{
    if(tree)
    {
        InOrderTraverse(tree->lchild);
        printf("%c ", tree->data);
        InOrderTraverse(tree->rchild);
    }
}

void PostOrderTraverse(PTree tree)
{
    if(tree)
    {
        PostOrderTraverse(tree->lchild);
        PostOrderTraverse(tree->rchild);
        printf("%c ", tree->data);
    }
}

void Destroy(PTree tree)
{
    if(!tree)
        return;

    Destroy(tree->lchild);
    Destroy(tree->rchild);

    printf("free %c\n", tree->data);
    free(tree);
}
